package Tests;

public class AmazonCodeTest {
	public int findSortedArrayRotation(int[] array){
	    
	    return findTheRotationValue(array, 0, array.length);
	}

	//Works like a modified binary search to look through the array and spot the ratation value.
	//Complexity O(log n)
	public int findTheRotationValue(int[] array, int theBegin, int theEnd){
	    
	    if (theBegin > theEnd - 1 || array[theBegin] < array[theEnd - 1]){
	        System.out.println("Return 0");
	        return 0;
	    }
	    int theMiddle = (theBegin + theEnd)/2;
	    System.out.println("The middle is " + theMiddle);
	    int res = findTheRotationValue(array, theBegin, theMiddle);
	    if (res > 0){
	    	System.out.println("Return res " + res);
	        return res;
	    }
	    res = findTheRotationValue(array, theMiddle, theEnd);
	    if (res > 0){
	    	System.out.println("Return res " + res);
	        return res;
	    }
	    System.out.println("Return middle " + theMiddle);
	    return theMiddle;
	}
}
